package leetcode_100;

import java.util.ArrayList;
import java.util.List;



/**
 *@author 周杨
 *MergeIntervals_56 Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping. 
 *describe: 合并区间 AC 98%
 *2018年5月9日 下午2:56:30
 */
public class MergeIntervals_56 {
	List<Interval> res; 
	static class Interval {
		      int start;
		      int end;
		      Interval() { start = 0; end = 0; }
		      Interval(int s, int e) { start = s; end = e; }
		  }
	public static void main(String[] args) {
		MergeIntervals_56 test=new MergeIntervals_56();
		Interval a=new Interval(2, 3);
		Interval b=new Interval(4, 5);
		Interval c=new Interval(6,7);
		Interval d=new Interval(8,9);
		
		Interval e=new Interval(1,10);
		/*Interval a=new Interval(2, 3);
		Interval b=new Interval(5, 5);
		Interval c=new Interval(2,2);
		Interval d=new Interval(3,4);
		
		Interval e=new Interval(3,4);*/
		Interval f=new Interval(4, 5);
		List<Interval> intervals=new ArrayList<Interval>();
		intervals.add(a);
		intervals.add(b);
		intervals.add(c);
		intervals.add(d);
		intervals.add(e);
		//intervals.add(f);
		test.merge(intervals);

	}
	
	public List<Interval> merge(List<Interval> intervals) {
		this.res=new ArrayList<Interval>();
		boolean flag;//遍历哨兵
		for(Interval now:intervals) {
			do {
				flag=false;
				for(int i=0;i<this.res.size();++i) {
					Interval resObj=this.res.get(i);
					if(judge(now,resObj)) {//可以合并
						now=merge(now,resObj);
						flag=true;
						this.res.remove(i);
						flag=true;
						break;
					}
				}
				if(!flag)//如果没有发生合并
					break;
			}
			while(flag&&this.res.size()>0);
			this.res.add(now);
		}
		
        return this.res;
    }
	
	public boolean judge(Interval a,Interval b) {
		if(a.end<b.start)
			return false;
		if(b.end<a.start)
			return false;
		return true;
	}
	
	public Interval merge(Interval a,Interval b) {
		return new Interval(Math.min(a.start, b.start), Math.max(a.end,b.end));
	}

}
